package com.singzi.leetcode.N100;

public class T0062DyProgram {

    public static void main(String[] args) {
        Solution0062 solution0062 = new Solution0062();

        int m = 10;
        int n = 10;
        System.out.println(solution0062.uniquePaths(m, n));

    }
}
class Solution0062 {
    public int uniquePaths(int m, int n) {
        if(m==1||n==1) return 1;

        if(m==2&&n==2) return 2;

        // return uniquePaths(m,n-1)+uniquePaths(m-1,n);

        int [][]dp = new int[m][n];
        // dp[i][j] = dp[i][j-1] + dp[i-1][j];

        for(int i = 0;i < m;i++) dp[i][0] = 1;
        for(int j = 0;j < n;j++) dp[0][j] = 1;


        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[m-1][n-1];




    }


}